// 版权归Go作者所有。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 此文件实现nat到字符串的转换函数。

package big

import (
	"errors"
	"fmt"
	"io"
	"math"
	"math/bits"
	"sync"
)

const digits = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

// 注意：MaxBase=len（数字），但它必须保持非类型化的符文常量
// 以便与API兼容。

// MaxBase是字符串转换可接受的最大基数。
const MaxBase = 10 + ('z' - 'a' + 1) + ('Z' - 'A' + 1)
const maxBaseSmall = 10 + ('z' - 'a' + 1)

// maxPow返回（b**n，n），使得b**n是b**n的最大幂<==M.
// 例如，对于64位字中的19位十进制数字，maxPow（10）==（1e19，19）。
// 换言之，一个单词中最多有n个b基数字。
// TODO（gri）将其替换为生成时生成的表。
func maxPow(b Word) (p Word, n int) {
	p, n = b, 1 // 假设b<==M 
	for max := _M / b; p <= max; {
		// p==b**n和p<=max 
		p *= b
		n++
	}
	// p==b**n和p<==M 
	return
}

// pow为n>0返回x**n，否则返回1。
func pow(x Word, n int) (p Word) {
	// n==bi*2**i之和，对于0<=i<imax，bi是0或1 
	// 因此x**n==x**（2**i）对所有i的乘积，其中bi==1 
	// （俄罗斯农民指数法）
	p = 1
	for n > 0 {
		if n&1 != 0 {
			p *= x
		}
		x *= x
		n >>= 1
	}
	return
}

// 扫描错误
var (
	errNoDigits = errors.New("number has no digits")
	errInvalSep = errors.New("'_' must separate successive digits")
)

// 扫描与给定转换基中表示无符号数的r对应的最长前缀
// 的数。
// 扫描返回相应的自然数res、实际基数b、
// 一个数字计数，以及一个读取或语法错误err（如果有）。
// 
// 对于基数0，在基数
// 前缀和相邻数字之间，以及在连续数字之间，可能会出现下划线字符` ` `；这样的
// 下划线不会改变数字的值，或者返回的
// 数字计数。如果没有其他错误，下划线的错误位置将被报告为
// 错误。如果是基地！=0，下划线为
// 无法识别，因此终止扫描，就像任何其他不是有效小数点或数字的字符
// 一样。
// 
// /number=尾数|前缀pmantissa。
// prefix=“0”[“b”|“b”|“b”|“o”|“o”|“x”]。
// 尾数=位数”[数字]|数字|“数字。
// pmantissa=[““]位”[位数]|[““]位数|”数字。
// digits=位{[“”]digit}。
// digit=“0”。。。“9”|“a”。。。“z”|“A”。。。“Z”。
// 
// 除非设置了fracOk，否则基参数必须为0或介于
// 2和MaxBase之间的值。如果设置了fracOk，则基参数必须是
// 0、2、8、10或16中的一个。提供无效的基参数会导致run-
// 时间恐慌。
// 
// 对于基数0，数字前缀决定实际基数：
// /`0b'或`0b'的前缀选择基数2，`0o'或`0o'选择基数8，
// /`0x'或`0x'选择基数16。如果fracOk为false，则“0”前缀
// （后面紧跟数字）也会选择基数8。否则，
// 所选基数为10，不接受前缀。
// 
// 如果设置了fracOk，则允许在句点后加上小数部分。yi zhong
// 该计数值用于确定小数部分。
// 
// 对于小于等于36的基数，小写和大写字母被认为是相同的：
// 字母“a”到“z”和“a”到“z”代表数字值10到35。
// 对于大于36的基数，大写字母“A”到“Z”代表数字
// 值36到61。
// 
// 结果数字计数>0对应于解析的（非前缀）位数
// 。数字计数<=0表示存在一个周期（仅当设置了fracOk 
// 时），而-count表示找到的小数位数。
// 在这种情况下，扫描号码的实际值是res*b**count。
// 
func (z nat) scan(r io.ByteScanner, base int, fracOk bool) (res nat, b, count int, err error) {
	// reject invalid bases 
	baseOk := base == 0 ||
		!fracOk && 2 <= base && base <= MaxBase ||
		fracOk && (base == 2 || base == 8 || base == 10 || base == 16)
	if !baseOk {
		panic(fmt.Sprintf("invalid number base %d", base))
	}

	// prev对之前看到的字符进行编码：它是一个
	// （还有别的）。
	// 有效分隔符“”只能出现在数字
	// 之后，如果base==0。
	prev := '.'
	invalSep := false

	// 一个字符前瞻
	ch, err := r.ReadByte()

	// 确定实际基数
	b, prefix := base, 0
	if base == 0 {
		// 实际基数为10，除非有一个基数前缀
		b = 10
		if err == nil && ch == '0' {
			prev = '0'
			count = 1
			ch, err = r.ReadByte()
			if err == nil {
				// 可能是0b，0b，0o，0o，0x，0x 
				switch ch {
				case 'b', 'B':
					b, prefix = 2, 'b'
				case 'o', 'O':
					b, prefix = 8, 'o'
				case 'x', 'X':
					b, prefix = 16, 'x'
				default:
					if !fracOk {
						b, prefix = 8, '0'
					}
				}
				if prefix != 0 {
					count = 0 // 前缀不被计算
					if prefix != '0' {
						ch, err = r.ReadByte()
					}
				}
			}
		}
	}

	// 转换字符串
	// 算法：在di 
	// 中，以最多n个数字的组收集数字，然后对每个这样的组使用mulAddWW将它们添加到
	// 结果中。
	z = z[:0]
	b1 := Word(b)
	bn, n := maxPow(b1) // b1基最多n位适合单词
	di := Word(0)       // 0<=di<b1**i<bn 
	i := 0              // 0<=i<n 
	dp := -1            // 小数点位置
	for err == nil {
		if ch == '.' && fracOk {
			fracOk = false
			if prev == '_' {
				invalSep = true
			}
			prev = '.'
			dp = count
		} else if ch == '_' && base == 0 {
			if prev != '0' {
				invalSep = true
			}
			prev = '_'
		} else {
			// 将符文转换为数字值d1 
			var d1 Word
			switch {
			case '0' <= ch && ch <= '9':
				d1 = Word(ch - '0')
			case 'a' <= ch && ch <= 'z':
				d1 = Word(ch - 'a' + 10)
			case 'A' <= ch && ch <= 'Z':
				if b <= maxBaseSmall {
					d1 = Word(ch - 'A' + 10)
				} else {
					d1 = Word(ch - 'A' + maxBaseSmall)
				}
			default:
				d1 = MaxBase + 1
			}
			if d1 >= b1 {
				r.UnreadByte() // ch不再属于数字
				break
			}
			prev = '0'
			count++

			// 收集di 
			di = di*b1 + d1
			i++

			// 如果di为“满”，将其添加到结果
			if i == n {
				z = z.mulAddWW(z, bn, di)
				di = 0
				i = 0
			}
		}

		ch, err = r.ReadByte()
	}

	if err == io.EOF {
		err = nil
	}

	// 其他错误优先于无效分隔符
	if err == nil && (invalSep || prev == '_') {
		err = errInvalSep
	}

	if count == 0 {
		// 找不到数字
		if prefix == '0' {
			// 只有八进制前缀0（可能后跟分隔符和大于7的数字）；
			// 解释为十进制0 
			return z[:0], 10, 1, err
		}
		err = errNoDigits // 漏掉；结果将是0 
	}

	// 将剩余数字添加到结果
	if i > 0 {
		z = z.mulAddWW(z, pow(b1, i), di)
	}
	res = z.norm()

	// 调整分数计数，如果有任何
	if dp >= 0 {
		// 0<=dp<=count 
		count = dp - count
	}

	return
}

// utoa将x转换为给定基数中的ASCII表示形式；
// base必须介于2和MaxBase之间，包括2和MaxBase。
func (x nat) utoa(base int) []byte {
	return x.itoa(false, base)
}

// itoa与utoa类似，但如果neg&&x！=0.
func (x nat) itoa(neg bool, base int) []byte {
	if base < 2 || base > MaxBase {
		panic("invalid base")
	}

	// x==0 
	if len(x) == 0 {
		return []byte("0")
	}
	// len（x）>0 

	// 为转换分配缓冲区
	i := int(float64(x.bitLen())/math.Log2(float64(base))) + 1 // 最多关闭1 
	if neg {
		i++
	}
	s := make([]byte, i)

	// 分别转换两个基的幂和两个基的非幂
	if b := Word(base); b == b&-b {
		// 移位是以位为单位的基b位数
		shift := uint(bits.TrailingZeros(uint(b))) // 移位>0，因为b>=2 
		mask := Word(1<<shift - 1)
		w := x[0]         // 当前字
		nbits := uint(_W) // w 

		// /转换低有效字（包括前导零）
		for k := 1; k < len(x); k++ {
			// 转换全数字
			for nbits >= shift {
				i--
				s[i] = digits[w&mask]
				w >>= shift
				nbits -= shift
			}

			// 转换任何部分前导数字并前进到下一个字
			if nbits == 0 {
				// 没有剩余的部分数字，只需前进
				w = x[k]
				nbits = _W
			} else {
				// 当前单词w（=x[k-1]）和下一个单词x[k]
				w |= x[k] << nbits
				i--
				s[i] = digits[w&mask]

				// 前进
				w = x[k] >> (shift - nbits)
				nbits = _W - (shift - nbits)
			}
		}

		// 转换最重要单词w的数字（省略前导零）
		for w != 0 {
			i--
			s[i] = digits[w&mask]
			w >>= shift
		}

	} else {
		bb, ndigits := maxPow(b)

		// 构建bb*叶大小的连续平方表，用于细分
		// 结果（表！=nil）<=>（len（x）>叶大小>0）
		table := divisors(len(x), b, ndigits, bb)

		// 保留x，创建本地副本供convertWords 
		q := nat(nil).set(x)

		// 将q转换为b基中的字符串s 
		q.convertWords(s, b, ndigits, bb, table)

		// 带前导零
		// （x！=0；因此s必须包含至少一个非零位
		// 循环将终止）
		i = 0
		for s[i] == '0' {
			i++
		}
	}

	if neg {
		i--
		s[i] = '-'
	}

	return s[i:]
}

// 将q的字转换为s基中的b位。如果q很大，它通过使用列表除数的nat/nat除法递归地“一分为二”
// 。否则，它将使用
// 重复nat/字除法进行迭代转换。
// 
// 迭代方法通过n个divW（）调用处理n个单词，每个divW（）调用访问
// 增量缩短q，总共n+（n-1）+（n-2）…+2+1，或n（n+1）/2 divW（）s.
// 递归转换将q除以其近似平方根，得到两部分，每一半
// q的大小。在两半上使用迭代方法意味着2*（n/2）（n/2+1）/2 divW（）的
// 加上昂贵的长div（）。渐进地，在divW（）的1/2处，该比率是有利的，并且通过递归地拆分子块，
// 变得更好。最好的方法是拆分块，直到多拆分一个
// 拆分所需的时间（因为nat/nat div（））比
// 迭代方法的两倍多。该阈值由叶大小表示。
// 范围2.中叶大小的基准测试。。64显示8和16的值运行良好，在中等长度时加速4倍，在20000位时加速367
// 特定硬件的leafSize。
// 
func (q nat) convertWords(s []byte, b Word, ndigits int, bb Word, table []divisor) {
	// 递归拆分较大的块
	if table != nil {
		// len（q）>leafSize>0 
		var r nat
		index := len(table) - 1
		for len(q) > leafSize {
			// 如果可能，找到接近sqrt（q）的除数，但在任何情况下<q 
			maxLength := q.bitLen()     // /~=log2 q，或者至少将该位长度的最大可能q分解为两位数（q'*bbb+r），以形成独立的子块
			for index > 0 && table[index-1].nbits > minLength {
			}
			if table[index].nbits >= maxLength && table[index].bbb.cmp(q) >= 0 {
				index--
				if index < 0 {
					panic("internal inconsistency")
				}
			}

			q, r = q.div(r, q, table[index].bbb)

			// 转换子块并在s[：h]和s[h:]中收集结果
			h := len(s) - table[index].ndigits
			r.convertWords(s[h:], b, ndigits, bb, table[0:index])
			s = s[:h] // /==q.convertWords（s，b，ndigits，bb，table[0:index+1]）
		}
	}

	i := len(s)
	var r Word
	if b == 10 {
		// 对10进行硬编码，这里将其速度提高1.25倍（允许/和%by常量）
		for len(q) > 0 {
			// 提取最低有效的基bb“数字”
			q, r = q.divW(q, bb)
			for j := 0; j < ndigits && i > 0; j++ {
				i--
				// 避免%计算，因为r%10==r-int（r/10）*10；
				// 对于基准测试tring100000base10 
				// 和较小的字符串（但对于较大的字符串稍慢）
				t := r / 10
				s[i] = '0' + byte(r-t*10)
				r = t
			}
		}
	} else {
		for len(q) > 0 {
			// 提取最低有效，base bb“digit”
			q, r = q.divW(q, bb)
			for j := 0; j < ndigits && i > 0; j++ {
				i--
				s[i] = digits[r%b]
				r /= b
			}
		}
	}

	// 预先设置高阶零
	for i > 0 { // 同时需要更多前导零
		i--
		s[i] = '0'
	}
}

// 拆分大于leafSize字的块（或设置为0以禁用递归转换）
// 使用：go test-bench=“Leaf”
// 8和16对leafSize进行基准测试和配置leafSize在3.0 GHz Xeon“Clovertown”CPU上有效（128字节缓存线）
// 8和16在2.66 GHz Core 2 Duo“Penryn”CPU上有效
var leafSize int = 8 // 字大小二进制值的数量视为一个单片块

type divisor struct {
	bbb     nat // 除数
	nbits   int // 除数的位长（不包括前导零）~=log2（bbb）
	ndigits int // 根据输出基位数
}

var cacheBase10 struct {
	sync.Mutex
}

// EXPW计算x**y 
func (z nat) expWW(x, y Word) nat {
	return z.expNN(nat(nil).setWord(x), nat(nil).setWord(y), nil)
}

// 构造bb*leafSize的幂表以用于细分
func divisors(m int, b Word, ndigits int, bb Word) []divisor {
	// 仅在启用递归转换且x较大时计算表
	if leafSize == 0 || m <= leafSize {
		return nil
	}

	// 确定k，其中（bb**leafSize）**（2**k）>=sqrt（x）
	k := 1
	for words := leafSize; words < m>>1 && k < len(cacheBase10.table); words <<= 1 {
		k++
	}

	// 重用和扩展现有除数表或创建新除数表表
	var table []divisor // 对于b==10，表与cacheBase10重叠。表
	if b == 10 {
		cacheBase10.Lock()
		table = cacheBase10.table[0:k] // 重新使用旧表进行此转换
	} else {
		table = make([]divisor, k) // 为此转换创建新表
	}

	// 扩展表
	if table[k-1].ndigits == 0 {
		// 根据需要添加新项
		var larger nat
		for i := 0; i < k; i++ {
			if table[i].ndigits == 0 {
				if i == 0 {
					table[0].bbb = nat(nil).expWW(bb, Word(leafSize))
					table[0].ndigits = ndigits * leafSize
				} else {
					table[i].bbb = nat(nil).sqr(table[i-1].bbb)
					table[i].ndigits = 2 * table[i-1].ndigits
				}

				// 优化：利用宏块中聚合的额外位
				larger = nat(nil).set(table[i].bbb)
				for mulAddVWW(larger, larger, b, 0) == 0 {
					table[i].bbb = table[i].bbb.set(larger)
					table[i].ndigits++
				}

				table[i].nbits = table[i].bbb.bitLen()
			}
		}
	}

	if b == 10 {
		cacheBase10.Unlock()
	}

	return table
}
